我們如何用數學來描述連接社會的無形紐帶？無論是將貝拉·盧戈西與好萊塢影星相連的「貝克恩數」，還是基於鄰近關係聚類數據點的 貝克恩數 將貝拉·盧戈西與好萊塢影星相連，還是 相似性圖形 根據接近程度聚類數據點的 圖論 提供了正式語言 $G = (V, E)$ 來建模這些離散世界。
1. 圖形的結構
圖形的核心由一組 頂點 ($V$) 和一組 邊 ($E$) 所組成。然而，其規則取決於結構的不同：
- 簡單圖形： 最優雅的形式；它禁止 環 （將頂點與自身相連的邊）以及 平行邊 （相同兩點間的冗餘邊）。
- 多重圖： 允許環和平行邊，常被用來模擬同一對節點之間多種類型的互動（例如文字訊息與語音通話）。
- 孤立頂點： 若一個頂點 $v$ 沒有任何邊與之相連，則稱為孤立頂點，表示該物件在當前集合中沒有任何關係。
鄰近邏輯
在資料科學中，我們經常使用一個 不相似函數 來構建圖形：
$$s(v, w) = |p_1 - q_1| + |p_2 - q_2| + |p_3 - q_3|$$
只有當 $s(v, w)$ 低於特定閾值時，我們才會在 $v$ 與 $w$ 之間繪製一條邊，從而有效建立一個「鄰居」網絡。
2. 路徑、連通性與元件
一條 路徑 是由頂點與邊組成的序列。如果某條路徑不會重複訪問任何頂點，則稱為 簡單路徑。連通性是圖形的心跳：
- 連通圖： 圖中任意兩個頂點之間都存在 每一個 頂點組合之間的路徑。
- 元件： 若圖形不連通，則會分裂成若干互不相交的部分，稱為元件。每個元件都是最大連通子圖。
3. 子圖：子集的架構
子圖 $G' = (V', E')$ 是圖 $G$ 的一個子集，其中 $V'$ 中的每一頂點都在 $V$ 內，且 $E'$ 中的每一條邊所連接的頂點也都在 $V'$ 中。識別子圖對於在全局網絡中檢測局部模式至關重要。
🎯 核心原理：握手引理
在任何無向圖中，所有頂點度數的總和是邊數的兩倍。這意味著度數為奇數的頂點數量必須是偶數。
$$\sum_{v \in V} \text{deg}(v) = 2|E|$$